#include<bits/stdc++.h>//std-1
using namespace std;
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x : x ;
	return ;
}

int n,m;
int t,k;
int F[2005][2005];
int Ans[2005][2005];

void init()
{
	F[0][0]=1;
	for(int i=1;i<=2001;++i)
	{
		for(int j=1;j<=2001;++j)
		{
			F[i][j]=F[i-1][j]+F[i-1][j-1];
			F[i][j]%=k;
			Ans[i][j]=Ans[i-1][j]+Ans[i][j-1]-Ans[i-1][j-1];
			if((!F[i][j])&&j<=i)Ans[i][j]++;
		}
	}
	return ;
}

int main()
{
	freopen("problem.in","r",stdin);
	freopen("problem.out","w",stdout);
	read(t);read(k);
	init();
	while(t--)
	{
		read(n);read(m);
		printf("%d\n",Ans[n+1][m+1]);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
